# -*- coding=utf-8-*-
"""
@File:memory_selection
@Author:Created by Han X.Y
@Date:on 2021/7/12 19:15 
"""
"""
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-search
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

"""



class Solution:
    def search(self, nums, target):
        """
        基于二分法实现
        """
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left+right)>> 1
            if nums[mid] == target:
                return mid
            else:
                if nums[mid] > target:
                    right = mid-1
                else:
                    left =mid+1
            # print(f'left={left},right={right},nums[left]={nums[left]},nums[right]={nums[right]}')
        return -1


if __name__ == "__main__":
    s = Solution()
    nums1 = [-1, 0, 3, 5, 9, 12]
    target1 = 2
    nums2 = [-1, 0, 3, 5, 9, 12]
    target2 = 9
    nums3 = [5]
    target3 = 5
    for i,j in zip([nums1,nums2,nums3],[target1,target2,target3]):
        print(s.search(i,j))


"""
二分查找：
核心：mid加一还是减一，while用<=还是<

- 寻找一个数(基本的二分搜索)
int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
    }
    return -1;
}


mid=left+(right-left)//2
1.为什么while循环的条件中是<=，而不是<?
答：因为初始化right的赋值是len-1,即最后一个元素的索引
而不是len.这两者可能出现在不同功能的二分查找中，
前者相当于[left，right];
后者相当于[left,right)
这个区间就是每一次进行搜索的区间

停止条件：
if nums[mid]==target:
	return mid
如果没有找到，然后返回-1
left=right+1



#寻找左侧边界的二分搜索
int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; // 注意
    
    while (left < right) { // 注意
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; // 注意
        }
    }
    return left;
}


1.while用<而不是<=?
left=0 right=len
终止条件：left==right,此时搜索区间[left，right)为空，
所以可以正确终止



#寻找右侧边界的二分查找
int right_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0, right = nums.length;
    
    while (left < right) {
        int mid = (left + right) / 2;
        if (nums[mid] == target) {
            left = mid + 1; // 注意
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid;
        }
    }
    return left - 1; // 注意
}

https://leetcode-cn.com/problems/binary-search/solution/er-fen-cha-zhao-xiang-jie-by-labuladong/



"""
